package offerbook;

/**
 * 给定一个数组arr， 返回所有子数组的累加和中， 最大的累加和
 * 方式1：穷举所有子数组，分别求和
 * 方式2：见笔记
 * <p>
 * Created at 2019/10/27 0027 下午 10:59
 * {6,-3,-2,7,-15,1,2,2},
 * 连续子向量的最大和为8(从第0个开始,到第3个为止)。
 * 给一个数组，返回它的最大连续子序列的和
 */
public class Code31_GreatestSumOfSubArray {

    //方式1：穷举
    public static int getMaxSum(int[] arr) {
        if (arr == null)
            return 0;
        //遍历所有子串
        int max = 0;
        int res = Integer.MIN_VALUE;
        //当前其实位置为i，则j是从i开始一直到arr.length-1，遍历这中间的所有元素加起来
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                //这里是遍历当前子串的和
                max = 0;
                for (int index = i; index <= j; index++) {
                    max += arr[index];
                }
                //更新子串最大和
                res = Math.max(max, res);
            }
        }
        return res;
    }

    public static int getMaxSum1(int[] arr) {
        if (arr == null)
            return 0;
        int cur = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {

            cur += arr[i];

            max = Math.max(cur, max);

            if(cur < 0 ){
                cur = 0;
            }
        }
        return max;
    }

    /**
     * DP:
     * f(i)表示以第i个结尾的元素的和,则
     *
     * f(i) = arr[i]  -----f(i-1)<0
     * f(i) = arr[i] + f(i-1) --- f(i-1)>=0
     */
    public static int getMaxSum2(int[] arr) {
        if(arr == null || arr.length == 0){
            return  0;
        }

        int curSum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            // f(i-1)小于0，f(i) = arr[i]
            if(curSum < 0){
                curSum = arr[i];
            }else {
                curSum += arr[i];
            }

            max = Math.max(curSum,max);
        }
        return max;
    }
    //TODO  递归有问题
    public static int getMaxSum3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return process(arr,0,Integer.MIN_VALUE,0);
    }
    private static int process(int []arr,int index,int max,int curSum){
        if(index == arr.length){
            return max;
        }
        if(curSum < 0){
            int temp = process(arr,index+1,max,arr[index+1]);
            max = Math.max(max,temp);
        }else {
            int temp = process(arr,index+1,max,curSum+arr[index+1]);
            max = Math.max(max,temp);
        }
        return max;
    }


    public static void main(String[] args) {
        int []arr1 = {-1,-2,-1,-1,-2,-1,-1,-2,-1,-1,-2,-1,-1,-2,-1,-1,-2,-1,-1,-2,-1,-1,-2,-1
                ,-1,-2,-1,-1,-2,-1,-1,-2,-1,-1,-2,-1,-1,-2,-1,-1,-2,-1,-1,-2,-1,-1,-2,-1};
        System.out.println(getMaxSum(arr1));
        System.out.println(getMaxSum1(arr1));
        System.out.println(getMaxSum2(arr1));

        int[]arr2 = {1,2,3,0,-1,-2,3,-5};
        System.out.println(getMaxSum(arr2));
        System.out.println(getMaxSum1(arr2));
        System.out.println(getMaxSum2(arr2));


        System.out.println(getMaxSum3(arr1));
        System.out.println(getMaxSum3(arr2));
    }
}
